#define _CRT_SECURE_NO_WARNINGS
//#include <bits/stdc++.h>
//using namespace std;
//
//queue<string> n, v;
//int m;
//int main()
//{
//	cin >> m;
//	while (m--)
//	{
//		string op, name, que;
//		cin >> op;
//		if (op == "IN")
//		{
//			cin >> name >> que;
//			if (que == "N")
//			{
//				n.push(name);
//			}
//			if (que == "V")
//			{
//				v.push(name);
//			}
//		}
//		if (op == "OUT")
//		{
//			cin >> que;
//			if (que == "N")
//			{
//				n.pop();
//			}
//			if (que == "V")
//			{
//				v.pop();
//			}			
//		}
//	}
//	while(v.size())
//	{
//		cout << v.front() << endl;
//		v.pop();
//	}
//	while(n.size())
//	{
//		cout << n.front() << endl;
//		n.pop();
//	}	
//	return 0;
//}

//#include <bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//priority_queue <ll, vector<ll>, greater<ll>> st;
//int n, x1, x2, ret;
//int main()
//{
//	cin >> n;
//	while(n--)
//	{
//		int x; cin >> x;
//		st.push(x);
//	}
//	while(st.size() > 1)
//	{
//		x1 = st.top();
//		st.pop();
//		x2 = st.top();
//		st.pop();
//		st.push(x1 + x2);
//		ret += (x1 + x2);		
//	}
//	cout << ret << endl;
//	return 0;
//}

//#include <bits/stdc++.h>
//using namespace std;
//
//int n;
//const int N = 1e5 + 10;
//int a[N], b[N];
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> a[i];
//	sort(a+1,a+n+1);
//	for (int i = 1; i < n; i++) b[i] = abs(a[i+1] - a[i]);
//	int ret = *min_element(b+1,b+n);
//	cout << ret << endl;
//	return 0;
//}

//#include <bits/stdc++.h>
//using namespace std;
//
//priority_queue <int, vector<int>, greater<int>> st;
//int n, ret;
//int main()
//{
//	cin >> n;
//	while  (n--)
//	{
//		int x;
//		cin >> x;
//		st.push(x);
//	}
//	while (st.size() > 1)
//	{
//		int x1, x2;
//		x1 = st.top();
//		st.pop();
//		x2 = st.top();
//		st.pop();
//		st.push(x1 + x2);
//		ret += (x1 + x2);
//	}
//	cout << ret << endl;
//	return 0;
//}

//#include <bits/stdc++.h>
//using namespace std;
//const int N = 1e6;
//int a[N];
//int w, n, ret;
//int main()
//{
//	cin >> w >> n;
//	for (int i = 1; i <= n; i++) cin >> a[i];
//	sort(a+1,a+1+n);
//	int l = 1, r = n;
//	while (l <= r)
//	{
//		if (a[l] + a[r] <= w)
//		{
//			l++;
//		}
//		r--;
//		ret++;
//	}
//	cout << ret << endl;
//	return 0;
//}

